function ListNode(val, next) {
  this.val = (val===undefined ? 0 : val)
  this.next = (next===undefined ? null : next)
}
function createList(arr) {
  if(arr.length == 0)
    return null;
  let head = new ListNode(arr[0], null), headNode = head;
  for(let i = 1; i < arr.length; i++) {
    let temp = new ListNode(arr[i], null);
    head.next = temp;
    head = temp;
  }
  return headNode;
}
function showList(head) {
  while(head) {
    console.log(head.val);
    head = head.next;
  }
}

/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function(head) {
  head = createList(head);
  if(!head || !head.next) return head;
  let nodeList1 = [], nodeList2 = [], count = 1, temp = head, length = 0;
  while(temp) {
    length++;
    temp = temp.next;
  }
  let mid = Math.ceil(length / 2);
  temp = head;
  while(mid) {
    mid--;
    nodeList1.push(temp);
    temp = temp.next;
  }
  while(temp) {
    nodeList2.push(temp);
    temp = temp.next;
  }
  nodeList2 = nodeList2.reverse();
  let arr = [], i = 0, j = 0;
  count = 0;
  while(i < nodeList1.length || j < nodeList2.length) {
    if(count % 2) {
      if(j >= nodeList2.length) return;
      arr.push(nodeList2[j]);
      j++;
    } else {
      if(i >= nodeList1.length) return;
      arr.push(nodeList1[i]);
      i++;
    }
    count++;
  }
  for(let i = 1; i < arr.length; i++) {
    arr[i - 1].next = arr[i];
  }
  arr[arr.length - 1].next = null;
  return arr[0];
};
let head = [1,2,3,4];
console.log(reorderList(head));
// head = [1,2,3,4,5];
// console.log(reorderList(head));
